{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Operations to Make the Array K-Increasing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: kIncreasing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #使数组 K 递增的最少操作次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始包含 <code>n</code>&nbsp;个正整数的数组&nbsp;<code>arr</code>&nbsp;，和一个正整数&nbsp;<code>k</code>&nbsp;。</p>\n",
    "\n",
    "<p>如果对于每个满足&nbsp;<code>k &lt;= i &lt;= n-1</code>&nbsp;的下标&nbsp;<code>i</code>&nbsp;，都有&nbsp;<code>arr[i-k] &lt;= arr[i]</code>&nbsp;，那么我们称&nbsp;<code>arr</code>&nbsp;是 <strong>K</strong>&nbsp;<strong>递增</strong> 的。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>比方说，<code>arr = [4, 1, 5, 2, 6, 2]</code>&nbsp;对于&nbsp;<code>k = 2</code>&nbsp;是 K 递增的，因为：\n",
    "\n",
    "\t<ul>\n",
    "\t\t<li><code>arr[0] &lt;= arr[2] (4 &lt;= 5)</code></li>\n",
    "\t\t<li><code>arr[1] &lt;= arr[3] (1 &lt;= 2)</code></li>\n",
    "\t\t<li><code>arr[2] &lt;= arr[4] (5 &lt;= 6)</code></li>\n",
    "\t\t<li><code>arr[3] &lt;= arr[5] (2 &lt;= 2)</code></li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "\t<li>但是，相同的数组&nbsp;<code>arr</code>&nbsp;对于&nbsp;<code>k = 1</code>&nbsp;不是 K 递增的（因为&nbsp;<code>arr[0] &gt; arr[1]</code>），对于&nbsp;<code>k = 3</code>&nbsp;也不是 K 递增的（因为&nbsp;<code>arr[0] &gt; arr[3]</code>&nbsp;）。</li>\n",
    "</ul>\n",
    "\n",
    "<p>每一次 <strong>操作</strong>&nbsp;中，你可以选择一个下标&nbsp;<code>i</code> 并将&nbsp;<code>arr[i]</code> <strong>改成任意&nbsp;</strong>正整数。</p>\n",
    "\n",
    "<p>请你返回对于给定的 <code>k</code>&nbsp;，使数组变成 K 递增的 <strong>最少操作次数</strong>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>arr = [5,4,3,2,1], k = 1\n",
    "<b>输出：</b>4\n",
    "<strong>解释：\n",
    "</strong>对于 k = 1 ，数组最终必须变成非递减的。\n",
    "可行的 K 递增结果数组为 [5,<em><strong>6</strong></em>,<em><strong>7</strong></em>,<em><strong>8</strong></em>,<em><strong>9</strong></em>]，[<em><strong>1</strong></em>,<em><strong>1</strong></em>,<em><strong>1</strong></em>,<em><strong>1</strong></em>,1]，[<em><strong>2</strong></em>,<em><strong>2</strong></em>,3,<em><strong>4</strong></em>,<em><strong>4</strong></em>] 。它们都需要 4 次操作。\n",
    "次优解是将数组变成比方说 [<em><strong>6</strong></em>,<em><strong>7</strong></em>,<em><strong>8</strong></em>,<em><strong>9</strong></em>,<em><strong>10</strong></em>] ，因为需要 5 次操作。\n",
    "显然我们无法使用少于 4 次操作将数组变成 K 递增的。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>arr = [4,1,5,2,6,2], k = 2\n",
    "<b>输出：</b>0\n",
    "<strong>解释：</strong>\n",
    "这是题目描述中的例子。\n",
    "对于每个满足 2 &lt;= i &lt;= 5 的下标 i ，有 arr[i-2] &lt;=<b> </b>arr[i] 。\n",
    "由于给定数组已经是 K 递增的，我们不需要进行任何操作。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [4,1,5,2,6,2], k = 3\n",
    "<b>输出：</b>2\n",
    "<strong>解释：</strong>\n",
    "下标 3 和 5 是仅有的 3 &lt;= i &lt;= 5 且不满足 arr[i-3] &lt;= arr[i] 的下标。\n",
    "将数组变成 K 递增的方法之一是将 arr[3] 变为 4 ，且将 arr[5] 变成 5 。\n",
    "数组变为 [4,1,5,<em><strong>4</strong></em>,6,<em><strong>5</strong></em>] 。\n",
    "可能有其他方法将数组变为 K 递增的，但没有任何一种方法需要的操作次数小于 2 次。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= arr.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= arr[i], k &lt;= arr.length</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-operations-to-make-the-array-k-increasing](https://leetcode.cn/problems/minimum-operations-to-make-the-array-k-increasing/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-operations-to-make-the-array-k-increasing](https://leetcode.cn/problems/minimum-operations-to-make-the-array-k-increasing/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,4,3,2,1]\\n1', '[4,1,5,2,6,2]\\n2', '[4,1,5,2,6,2]\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kIncreasing(self, arr: List[int], k: int) -> int:\n",
    "        r = 0\n",
    "        n = len(arr)\n",
    "        for i in range(k):\n",
    "            g = []\n",
    "            o = 0\n",
    "            while i < n:\n",
    "                o += 1\n",
    "                idx = bisect_right(g,arr[i])\n",
    "                if idx == len(g):\n",
    "                    g.append(arr[i])\n",
    "                else:\n",
    "                    g[idx] = arr[i]\n",
    "                i += k\n",
    "            r += o - len(g)\n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kIncreasing(self, arr: List[int], k: int) -> int:\n",
    "        n = len(arr)\n",
    "        ans = 0\n",
    "        for i in range(k):\n",
    "            f = list()\n",
    "            j, length = i, 0\n",
    "            while j < n:\n",
    "                length += 1\n",
    "                it = bisect_right(f, arr[j])\n",
    "                if it == len(f):\n",
    "                    f.append(arr[j])\n",
    "                else:\n",
    "                    f[it] = arr[j]\n",
    "                j += k\n",
    "            ans += length - len(f)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kIncreasing(self, arr: List[int], k: int) -> int: \n",
    "        n = len(arr)\n",
    "        ans = 0\n",
    "        for i in range(k):\n",
    "            j, lenn = i, 0\n",
    "            ls = []\n",
    "            while j < n:\n",
    "                lenn += 1\n",
    "                ind = bisect_right(ls, arr[j])\n",
    "                if ind == len(ls):\n",
    "                    ls.append(arr[j])\n",
    "                else:\n",
    "                    ls[ind] = arr[j]\n",
    "                j += k\n",
    "            ans += lenn - len(ls)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def kIncreasing(self, arr: List[int], k: int) -> int:\n",
    "        n = len(arr)  #  总长度 减去 最长非下降子序列 LIS 最长上升子序列\n",
    "        ans = 0\n",
    "        for i in range(k):  # 起点\n",
    "            SIZE = 1 + (n - 1 - i) // k\n",
    "            # f[i] 表示长度为i的最长上升子序列的末尾元素的最小值, 数组的值一定单调不降\n",
    "            f = []\n",
    "            for j in range(i, n, k):\n",
    "                idx = bisect_right(f, arr[j])\n",
    "                if idx == len(f):\n",
    "                    f.append(arr[j])\n",
    "                else:\n",
    "                    f[idx] = arr[j]\n",
    "            ans += SIZE - len(f)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kIncreasing(self, arr: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(k):\n",
    "            small_arr = arr[i::k]\n",
    "            end = []\n",
    "            m = len(small_arr)\n",
    "            for x in small_arr:\n",
    "                index = bisect_right(end, x)\n",
    "                if index == len(end):\n",
    "                    end.append(x)\n",
    "                else:\n",
    "                    end[index] = x\n",
    "            ans += m - len(end)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kIncreasing(self, arr: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        for i in range(k):\n",
    "            sorted_arr = []\n",
    "            for e in arr[i::k]:\n",
    "                index = bisect_right(sorted_arr, e)\n",
    "                if index == len(sorted_arr):\n",
    "                    sorted_arr.append(e)\n",
    "                else:\n",
    "                    sorted_arr[index] = e\n",
    "                    res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kIncreasing(self, arr: List[int], k: int) -> int:\n",
    "    \tsave = 0\n",
    "    \tn = len(arr)\n",
    "    \tfor i in range(min(k, n)):\n",
    "    \t\tf = []\n",
    "    \t\tfor j in range(i, n, k):\n",
    "    \t\t\tv = arr[j]\n",
    "    \t\t\tp = bisect.bisect_left(f, v+1)\n",
    "    \t\t\tif p < len(f):\n",
    "    \t\t\t\tf[p] = v\n",
    "    \t\t\telse:\n",
    "    \t\t\t\tf.append(v)\n",
    "    \t\tsave += len(f)\n",
    "    \t\n",
    "    \treturn len(arr) - save"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kIncreasing(self, arr: List[int], k: int) -> int:\n",
    "        save = 0\n",
    "        n = len(arr)\n",
    "        for i in range(min(k, n)):\n",
    "            f = []\n",
    "            for j in range(i, n, k):\n",
    "                v = arr[j]\n",
    "                if (p := bisect.bisect_left(f, v+1)) < len(f):\n",
    "                    f[p] = v\n",
    "                else:\n",
    "                    f.append(v)\n",
    "            save += len(f)\n",
    "        \n",
    "        return len(arr) - save"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kIncreasing(self, arr: List[int], k: int) -> int:\n",
    "        n = len(arr)\n",
    "\n",
    "        def maxIncreaseSeq(start):\n",
    "            stack = [0]\n",
    "            for i in range(start, n, k):\n",
    "                L, R = 0, len(stack)-1\n",
    "                while L <= R:\n",
    "                    mid = (L + R) // 2\n",
    "                    if stack[mid] <= arr[i]:\n",
    "                        L = mid + 1\n",
    "                    else:\n",
    "                        R = mid - 1\n",
    "                if L == len(stack):\n",
    "                    stack.append(arr[i])\n",
    "                else:\n",
    "                    stack[L] = arr[i]\n",
    "            return (n - start - 1) // k - len(stack) + 2\n",
    "\n",
    "        cnt = 0\n",
    "        for i in range(k):\n",
    "            cnt += maxIncreaseSeq(i)\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import *\n",
    "from queue import PriorityQueue\n",
    "from typing import *\n",
    "from heapq import *\n",
    "from functools import lru_cache\n",
    "# by hangpengjie\n",
    "class Solution:\n",
    "    def kIncreasing(self, arr: List[int], k: int) -> int:\n",
    "        n = len(arr)\n",
    "        p = 0\n",
    "        # note: there is [0,k)\n",
    "        for i in range(0,k):\n",
    "            a = []\n",
    "            for j in range(i,n,k):\n",
    "                if not a or arr[j] >= a[-1]:\n",
    "                    a.append(arr[j])\n",
    "                    continue\n",
    "                l,r = 0, len(a)-1\n",
    "                while l < r:\n",
    "                    m = (l + r) >> 1\n",
    "                    if a[m] > arr[j]:\n",
    "                        r = m\n",
    "                    else:\n",
    "                        l = m + 1\n",
    "                a[l] = arr[j]\n",
    "            p += len(a)\n",
    "        return len(arr) - p\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kIncreasing(self, arr: List[int], k: int) -> int:\n",
    "        N = len(arr)\n",
    "        not_move = 0\n",
    "        for s in range(k):\n",
    "            queue = []\n",
    "            for i in range(s, N, k):\n",
    "                if len(queue) == 0:\n",
    "                    queue.append(arr[i])\n",
    "                else:\n",
    "                    idx = bisect_right(queue, arr[i])\n",
    "                    if idx == len(queue):\n",
    "                        queue.append(arr[i])\n",
    "                    else:\n",
    "                        queue[idx] = min(queue[idx], arr[i])\n",
    "            not_move += len(queue)\n",
    "        return N - not_move\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kIncreasing(self, arr: List[int], k: int) -> int:\n",
    "        n = len(arr)\n",
    "\n",
    "        def maxIncreaseSeq(start):\n",
    "            stack = [0]\n",
    "            for i in range(start, n, k):\n",
    "                L, R = 0, len(stack)-1\n",
    "                while L <= R:\n",
    "                    mid = (L + R) // 2\n",
    "                    if stack[mid] <= arr[i]:\n",
    "                        L = mid + 1\n",
    "                    else:\n",
    "                        R = mid - 1\n",
    "                if L == len(stack):\n",
    "                    stack.append(arr[i])\n",
    "                else:\n",
    "                    stack[L] = arr[i]\n",
    "            return (n - start - 1) // k - len(stack) + 2\n",
    "\n",
    "        cnt = 0\n",
    "        for i in range(k):\n",
    "            cnt += maxIncreaseSeq(i)\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kIncreasing(self, arr: List[int], k: int) -> int:\n",
    "        def lis(a):\n",
    "            t = []\n",
    "            for x in a:\n",
    "                i = bisect_right(t, x)\n",
    "                if i == len(t):\n",
    "                    t.append(x)\n",
    "                else:\n",
    "                    t[i] = x\n",
    "            return len(t)\n",
    "        ans = 0\n",
    "        for i in range(k):\n",
    "            ans += lis(arr[i::k])\n",
    "        return len(arr) - ans\n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kIncreasing(self, arr: List[int], k: int) -> int:\n",
    "        n = len(arr)\n",
    "        ans = 0\n",
    "        for i in range(k):\n",
    "            f = list()\n",
    "            j, length = i, 0\n",
    "            while j < n:\n",
    "                length += 1\n",
    "                it = bisect_right(f, arr[j])\n",
    "                if it == len(f):\n",
    "                    f.append(arr[j])\n",
    "                else:\n",
    "                    f[it] = arr[j]\n",
    "                j += k\n",
    "            ans += length - len(f)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kIncreasing(self, arr: List[int], k: int) -> int:\n",
    "        def go(lst):\n",
    "            n = len(lst)\n",
    "            dp = [0] * n\n",
    "            dp[0] = lst[0]\n",
    "            idx = 0\n",
    "            for i in range(1, n):\n",
    "                l, r = 0, idx\n",
    "                while l <= r:\n",
    "                    m = l + r >> 1\n",
    "                    if dp[m] <= lst[i]:\n",
    "                        l = m + 1\n",
    "                    else:\n",
    "                        r = m - 1\n",
    "                if l > idx:\n",
    "                    idx += 1\n",
    "                dp[l] = lst[i]\n",
    "                # print(lst[i], lst, dp, idx, l)\n",
    "            return n - (idx + 1)\n",
    "        \n",
    "        ret = 0\n",
    "        n = len(arr)\n",
    "        for i in range(k):\n",
    "            incr = go(arr[i:n:k])\n",
    "            ret += incr\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kIncreasing(self, arr: List[int], k: int) -> int:\n",
    "        N = len(arr)\n",
    "        L = (N+k-1)//k + 1\n",
    "        minByLens = [0]*L\n",
    "        inf = float('inf')\n",
    "        res = 0\n",
    "        for start in range(k):\n",
    "            for i in range(L):\n",
    "                minByLens[i] = inf\n",
    "            minByLens[0] = 0\n",
    "            for n in arr[start::k]:\n",
    "                off = bisect_right(minByLens, n)\n",
    "                minByLens[off] = n\n",
    "            res += (N+k-1-start)//k - bisect_left(minByLens, inf) + 1\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kIncreasing(self, arr: List[int], k: int) -> int:\n",
    "        n=len(arr)\n",
    "        ans=0\n",
    "        for i in range(k):\n",
    "            d=[arr[i]]\n",
    "            tot=1\n",
    "            for j in range(i+k,n,k):\n",
    "                tot+=1\n",
    "                x=bisect.bisect_right(d,arr[j])\n",
    "                if x==len(d):\n",
    "                    d.append(arr[j])\n",
    "                else:\n",
    "                    d[x]=arr[j]\n",
    "            ans+=tot-len(d)\n",
    "        return ans\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "class Solution:\n",
    "    def kIncreasing(self, arr: List[int], k: int) -> int:\n",
    "        n = len(arr)\n",
    "        ans = 0\n",
    "        for i in range(k):\n",
    "            f = list()\n",
    "            j, length = i, 0\n",
    "            while j < n:\n",
    "                length += 1\n",
    "                it = bisect_right(f, arr[j])\n",
    "                if it == len(f):\n",
    "                    f.append(arr[j])\n",
    "                else:\n",
    "                    f[it] = arr[j]\n",
    "\n",
    "                j += k \n",
    "            ans += length - len(f)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kIncreasing(self, arr: List[int], k: int) -> int:\n",
    "        def bs(ends,length,num):\n",
    "            l = 0\n",
    "            ans = -1\n",
    "            r = length-1\n",
    "            while l<=r:\n",
    "                m = (l+r)//2\n",
    "                if ends[m]>num:\n",
    "                    ans = m\n",
    "                    r = m-1\n",
    "                else:\n",
    "                    l = m+1\n",
    "            return ans\n",
    "        def lengthOfNoDecreasing(size):\n",
    "            m = size\n",
    "            ends = [0]*m\n",
    "            length = 0\n",
    "            for i in range(m):\n",
    "                find = bs(ends,length,nums[i])\n",
    "                if find==-1:\n",
    "                    ends[length] = nums[i]\n",
    "                    length += 1\n",
    "                else:\n",
    "                    ends[find] = nums[i]\n",
    "            return length\n",
    "\n",
    "        n = len(arr)\n",
    "        ans = 0\n",
    "        nums = [0]*100001\n",
    "        for i in range(k):\n",
    "            size = 0\n",
    "            for j in range(i,n,k):\n",
    "                nums[size] = arr[j]\n",
    "                size += 1\n",
    "            ans += size - lengthOfNoDecreasing(size)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kIncreasing(self, arr: List[int], k: int) -> int:\n",
    "        def find(i, lens, ends):\n",
    "            l = 0\n",
    "            r = lens - 1\n",
    "            ans = -1\n",
    "            while l <= r:\n",
    "                mid = (l+r) // 2\n",
    "                if nums[i] < ends[mid]:\n",
    "                    r = mid - 1\n",
    "                    ans = mid\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            return ans\n",
    "        def size1(a):\n",
    "            ends = [0 for _ in range(len(a))]\n",
    "            lens = 0\n",
    "            for i in range(len(a)):\n",
    "                m = find(i, lens, ends)\n",
    "                if m == -1:\n",
    "                    ends[lens] = a[i]\n",
    "                    lens += 1\n",
    "                else:\n",
    "                    ends[m] = a[i]\n",
    "            return lens\n",
    "        n = len(arr)\n",
    "        ans = 0\n",
    "        nums = [0 for _ in range(n)]\n",
    "        for i in range(k):\n",
    "            size = 0\n",
    "            for j in range(i, n, k):\n",
    "                nums[size] = arr[j]\n",
    "                size += 1\n",
    "            ans += size - size1(nums[:size])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "dp = [0] * 100000\r\n",
    "class Solution:\r\n",
    "    def kIncreasing(self, arr: List[int], k: int) -> int:\r\n",
    "        n = len(arr)\r\n",
    "\r\n",
    "        def lis(i: int) -> int:\r\n",
    "            m = 0\r\n",
    "            for j in range(i, n, k):\r\n",
    "                lo = 0\r\n",
    "                hi = m\r\n",
    "                while lo < hi:\r\n",
    "                    mid = lo + hi >> 1\r\n",
    "                    if dp[mid] > arr[j]:\r\n",
    "                        hi = mid\r\n",
    "                    else:\r\n",
    "                        lo = mid + 1\r\n",
    "                \r\n",
    "                dp[lo] = arr[j]\r\n",
    "                if lo == m: m += 1\r\n",
    "\r\n",
    "            return m\r\n",
    "        \r\n",
    "        return n - sum(map(lis, range(k)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kIncreasing(self, arr: List[int], k: int) -> int:\n",
    "        def find(i, lens, ends):\n",
    "            l = 0\n",
    "            r = lens - 1\n",
    "            ans = -1\n",
    "            while l <= r:\n",
    "                mid = (l+r) // 2\n",
    "                if nums[i] < ends[mid]:\n",
    "                    r = mid - 1\n",
    "                    ans = mid\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            return ans\n",
    "        def size1(a):\n",
    "            ends = [0 for _ in range(len(a))]\n",
    "            lens = 0\n",
    "            for i in range(len(a)):\n",
    "                m = find(i, lens, ends)\n",
    "                if m == -1:\n",
    "                    ends[lens] = a[i]\n",
    "                    lens += 1\n",
    "                else:\n",
    "                    ends[m] = a[i]\n",
    "            return lens\n",
    "        n = len(arr)\n",
    "        ans = 0\n",
    "        nums = [0 for _ in range(n)]\n",
    "        for i in range(k):\n",
    "            size = 0\n",
    "            for j in range(i, n, k):\n",
    "                nums[size] = arr[j]\n",
    "                size += 1\n",
    "            ans += size - size1(nums[:size])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "dp = [0] * 100000\r\n",
    "class Solution:\r\n",
    "    def kIncreasing(self, arr: List[int], k: int) -> int:\r\n",
    "        n = len(arr)\r\n",
    "        res = n\r\n",
    "\r\n",
    "        for i in range(k):\r\n",
    "            m = 0\r\n",
    "            for j in range(i, n, k):\r\n",
    "                lo = 0\r\n",
    "                hi = m\r\n",
    "                while lo < hi:\r\n",
    "                    mid = lo + hi >> 1\r\n",
    "                    if dp[mid] > arr[j]:\r\n",
    "                        hi = mid\r\n",
    "                    else:\r\n",
    "                        lo = mid + 1\r\n",
    "                \r\n",
    "                dp[lo] = arr[j]\r\n",
    "                if lo == m: m += 1\r\n",
    "            res -= m\r\n",
    "        \r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kIncreasing(self, arr: List[int], k: int) -> int:\n",
    "        n = len(arr)\n",
    "        # 求最长递增子序列长度\n",
    "        def ans_per_subarr(arr: List[int]):\n",
    "            n = len(arr)\n",
    "            q = [0] * (n + 10)\n",
    "            ln = 0\n",
    "            for i in range(n):\n",
    "                l, r = 0, ln\n",
    "                while l < r:\n",
    "                    mid = l + r + 1 >> 1\n",
    "                    if q[mid] <= arr[i]: l = mid\n",
    "                    else: r = mid - 1\n",
    "                ln = max(ln, r + 1)\n",
    "                q[r + 1] = arr[i]\n",
    "            return n - ln\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(k):\n",
    "            res = [x for x in arr[i:n:k]]\n",
    "            ans += ans_per_subarr(res)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kIncreasing(self, arr: List[int], k: int) -> int:\n",
    "        def f(L):\n",
    "            k = [L[0]]\n",
    "            for i in L[1:]:\n",
    "                pos = bisect_right(k,i)\n",
    "                if pos == len(k):k.append(i)\n",
    "                else:k[pos] = i\n",
    "            return len(L)-len(k)\n",
    "        return sum([f(arr[i::k]) for i in range(k)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def kIncreasing(self, arr: List[int], k: int) -> int:\r\n",
    "        res = len(arr)\r\n",
    "\r\n",
    "        g = [[] for _ in range(k)]\r\n",
    "        for i,x in enumerate(arr):\r\n",
    "            g[i % k].append(x)\r\n",
    "\r\n",
    "        def lcs(arr: List[int]) -> int :\r\n",
    "            st = []\r\n",
    "            for x in arr:\r\n",
    "                j = bisect_right(st, x)\r\n",
    "                if j == len(st):\r\n",
    "                    st.append(x)\r\n",
    "                else:\r\n",
    "                    st[j] = x \r\n",
    "            return len(st)\r\n",
    "    \r\n",
    "        for v in g:\r\n",
    "            res -= lcs(v)\r\n",
    "        # 不能贪心\r\n",
    "        # for i in range(len(arr) - k):\r\n",
    "        #     if arr[i] > arr[i + k]:\r\n",
    "        #         res += 1\r\n",
    "        return res "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
